package com.math;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class NewLevelTraversal {
    public static void main(String[] args) {

        NewTreeNode root = new NewTreeNode(0);
        NewTreeNode root1 = new NewTreeNode(1);
        NewTreeNode root2 = new NewTreeNode(2);
        NewTreeNode root3 = new NewTreeNode(3);
        NewTreeNode root4 = new NewTreeNode(4);
        NewTreeNode root5 = new NewTreeNode(5);
        NewTreeNode root6 = new NewTreeNode(6);

        root.left = root1;
        root.right = root2;
        root1.left = root3;
        root1.right = root4;
        root2.left = root5;
        root2.right = root6;

        System.out.println("二叉树按层级遍历");
        List<ArrayList<Integer>> list =  NewLevelTraversal.getOrder(root);
        for (ArrayList<Integer> list1: list) {
            System.out.println(list1);
        }
        System.out.println("二叉树先序遍历");
        NewLevelTraversal.getDeepOrder(root);
    }

    //二叉树按层级遍历
    private static List<ArrayList<Integer>> getOrder(NewTreeNode root) {
        List<ArrayList<Integer>> result = new ArrayList<>();
        LinkedList<NewTreeNode> linkedList = new LinkedList<>();
        if (root != null) {
            linkedList.add(root);
        }
        int size = linkedList.size();
        while (size > 0) {
            ArrayList<Integer> item = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                NewTreeNode node = linkedList.remove();
                item.add(node.val);
                if (node.left != null) {
                    linkedList.add(node.left);
                }
                if (node.right != null) {
                    linkedList.add(node.right);
                }
            }
            result.add(item);
            size = linkedList.size();
        }
        return result;
    }

    //二叉树先序遍历
    private static void getDeepOrder(NewTreeNode root) {
        //使用递归的方法，递归，就是方法调用自己
        //先序遍历，先输出根的值，再输出左子树的值，再输出右子树的值
        if (root != null) {
            //输出根的值
            System.out.println(root.val);
            //输出左子树的值
            NewTreeNode left = root.left;
            getDeepOrder(left);
            //输出右子树的值
            NewTreeNode right = root.right;
            getDeepOrder(right);
        }
    }
}
